Art Gallery Theorems and Algorithms

Art Gallery Theorems and Algorithms is a mathematical monograph on topics related to the art gallery problem, on finding positions for guards within a polygonal museum floorplan so that all points of the museum are visible to at least one guard, and on related problems in computational geometry concerning polygons. It was written by Joseph O'Rourke, and published in 1987 in the International Series of Monographs on Computer Science of the Oxford University Press. Only 1000 copies were produced before the book went out of print, so to keep this material accessible O'Rourke has made a pdf version of the book available online.

Topics

The art gallery problem, posed by Victor Klee in 1973, asks for the number of points at which to place guards inside a polygon (representing the floor plan of a museum) so that each point within the polygon is visible to at least one guard. Václav Chvátal provided the first proof that the answer is at most [math]\displaystyle{ \lceil n/3\rceil }[/math] for a polygon with [math]\displaystyle{ n }[/math] corners, but a simplified proof by Steve Fisk based on graph coloring and polygon triangulation is more widely known. This is the opening material of the book, which goes on to covers topics including visibility, decompositions of polygons, coverings of polygons, triangulations and triangulation algorithms, and higher-dimensional generalizations, including the result that some polyhedra such as the Schönhardt polyhedron do not have triangulations without additional vertices. More generally, the book has as a theme "the interplay between discrete and computational geometry".

It has 10 chapters, whose topics include the original art gallery theorem and Fisk's triangulation-based proof; rectilinear polygons; guards that can patrol a line segment rather than a single point; special classes of polygons including star-shaped polygons, spiral polygons, and monotone polygons; non-simple polygons; prison yard problems, in which the guards must view the exterior, or both the interior and exterior, of a polygon; visibility graphs; visibility algorithms; the computational complexity of minimizing the number of guards; and three-dimensional generalizations.

Audience and reception

The book only requires an undergraduate-level knowledge of graph theory and algorithms. However, it lacks exercises, and is organized more as a monograph than as a textbook. Despite warning that it omits some details that would be important to implementors of the algorithms that it describes, and does not describe algorithms that perform well on random inputs despite poor worst-case complexity, reviewer Wm. Randolph Franklin recommends it "for the library of every geometer".

Reviewer Herbert Edelsbrunner writes that "This book is the most comprehensive collection of results on polygons currently available and thus earns its place as a standard text in computational geometry. It is very well written and a pleasure to read." However, reviewer Patrick J. Ryan complains that some of the book's proofs are inelegant, and reviewer David Avis, writing in 1990, noted that already by that time there were "many new developments" making the book outdated. Nevertheless, Avis writes that "the book succeeds on a number of levels", as an introductory text for undergraduates or for researchers in other areas, and as an invitation to solve the "many unsolved questions" remaining in this area.